翻訳と辞書 Words near each other ・ Constraint algebra ・ Constraint algorithm ・ Constraint automaton ・ Constraint Composite Graph ・ Constraint counting ・ Constraint Grammar ・ Constraint graph ・ Constraint graph (layout) ・ Constraint Handling Rules ・ Constraint inference ・ Constraint learning ・ Constraint logic programming ・ Constraint programming ・ Constraint satisfaction ・ Constraint satisfaction dual problem ・ Constraint satisfaction problem ・ Constraint-based Routing Label Distribution Protocol ・ Constraint-induced movement therapy ・ Constraints accounting ・ Constricta ・ Constricta (fungus) ・ Constricted elimia ・ Constricting Rage of the Merciless ・ Constriction ・ Constriction of video ・ Constriction ring syndrome ・ Constrictive pericarditis ・ Constrictivity ・ Constrictor ・ Constrictor (album) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Constraint satisfaction problem ： ウィキペディア英語版 Constraint satisfaction problem Constraint satisfaction problems (CSPs) are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. The boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT) and answer set programming (ASP) can be roughly thought of as certain forms of the constraint satisfaction problem. Examples of simple problems that can be modeled as a constraint satisfaction problem * Eight queens puzzle * Map coloring problem * Sudoku, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato and many other logic puzzles. Examples demonstrating the above are often provided with tutorials of ASP, boolean SAT and SMT solvers. In the general case, constraint problems can be much harder, and may not be expressible in some of these simpler systems. "Real life" examples include automated planning〔(Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning ), Ian Miguel - slides.〕 and resource allocation. ==Formal definition== Formally, a constraint satisfaction problem is defined as a triple $\backslash langle\; X,D,C\; \backslash rangle$, where : $X\; =\; \backslash$ is a set of variables, : $D\; =\; \backslash$ is a set of the respective domains of values, and : $C\; =\; \backslash$ is a set of constraints. Each variable $X\_i$ can take on the values in the nonempty domain $D\_i$. Every constraint $C\_j\; \backslash in\; C$ is in turn a pair $\backslash langle\; t\_j,R\_j\; \backslash rangle$, where $t\_j\; \backslash subset\; X$ is a subset of $k$ variables and $R\_j$ is an $k$-ary relation on the corresponding subset of domains $D\_j$. An ''evaluation'' of the variables is a function from a subset of variables to a particular set of values in the corresponding subset of domains. An evaluation $v$ satisfies a constraint $\backslash langle\; t\_j,R\_j\; \backslash rangle$ if the values assigned to the variables $t\_j$ satisfies the relation $R\_j$. An evaluation is ''consistent'' if it does not violate any of the constraints. An evaluation is ''complete'' if it includes all variables. An evaluation is a ''solution'' if it is consistent and complete; such an evaluation is said to ''solve'' the constraint satisfaction problem. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Constraint satisfaction problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.